#ifndef HEAP_SORT
#define HEAP_SORT

#include "swap.c"

// 从 startIdx 开始的位置向下调整，让数组变为堆
void percDown(ElementType a[], int startIdx, int length) {
    int parent, child;
    // 取出 startIdx 处存放的值
    ElementType temp = a[startIdx];
    // 向下（左右儿子）找可以正确存放 temp 的合适位置
    for (parent = startIdx; parent*2+1 < length; parent = child /* 顺着调整过的儿子节点继续向下 */) {
        child = parent*2+1;
        if ((child != length - 1) && comparator(a[child], a[child+1]) < 0) {
            // 有右儿子，且右儿子比较大
            child++; // 指向右儿子
        }
        if (comparator(temp, a[child]) >= 0) {
            // temp 比它的左右儿子都大，即找到了合适位置，不用再往下找了
            break;
        }
        // 把更大的子节点复制到父节点位置，即把大的数往上调
        a[parent] = a[child];
    }
    a[parent] = temp;
}

// 堆排序, 选择排序的一种，先建立最大堆，然后把堆顶元素和最后一个元素交换，然后把剩下的元素重新调整为最大堆，重复这个过程
void heap_Sort(ElementType a[], int length) {
    // 建立最大堆
    for (int i=length/2; i >= 0; i--) {
        percDown(a, i, length);
    }
    // 排序
    for (int i=length-1; i > 0; i--) {
        // 把堆顶元素和最后一个元素交换
        swap(&a[0], &a[i]);
        percDown(a, 0, i);
    }
}

#endif
